#include "tools/hash_map.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 默认初始大小， 初始容量
#define INITIAL_CAPACITY 16
// 负载因子阀值， 超过这个值时，会自动扩容
#define LOAD_FACTOR 0.75

// 哈希函数
unsigned int hash(const char *key, int capcity) {
    unsigned int hash_value = 0;
    for (int i = 0; key[i] != '\0'; i++) {
        hash_value = hash_value * 31 + key[i];
    }
    return hash_value % capcity;
}

// 创建新节点
Node *create_node(const char *key, void *value) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->key = strdup(key);   // 复制键
    node->value = value;       // 存储值
    node->next = NULL;
    return node;
}

// 初始化哈希表
HashMap *create_hashmap() {
    HashMap *hashmap = (HashMap *)malloc(sizeof(HashMap));
    hashmap->capacity = INITIAL_CAPACITY;
    hashmap->size = 0;
    hashmap->buckets = (Node **)calloc(hashmap->capacity, sizeof(Node *));   // 初始化数组
    return hashmap;
}

// 扩容哈希表
void hashmap_resize(HashMap *hashmap) {
    int new_capacity = hashmap->capacity * 2;
    Node **new_buckets = (Node **)calloc(new_capacity, sizeof(Node *));
    // 重新构造所有哈希值
    for (int i = 0; i < hashmap->capacity; i++) {
        Node *current_node = hashmap->buckets[i];
        while (current_node != NULL) {
            Node *next_node = current_node->next;
            unsigned int new_index = hash(current_node->key, new_capacity);

            // 数据重新放入新容器中
            current_node->next = new_buckets[new_index];
            new_buckets[new_index] = current_node;

            current_node = next_node;
        }
    }
    // 释放旧容器
    free(hashmap->buckets);
    hashmap->buckets = new_buckets;
    hashmap->capacity = new_capacity;
}

// 插入键值对
void hashmap_insert(HashMap *hashmap, const char *key, void *value) {
    // 检查是否需要扩容
    if ((double)hashmap->size / hashmap->capacity >= LOAD_FACTOR) {
        hashmap_resize(hashmap);
    }

    unsigned int index = hash(key, hashmap->capacity);
    Node *node = create_node(key, value);

    // 插入到链表头部
    node->next = hashmap->buckets[index];
    hashmap->buckets[index] = node;
    hashmap->size++;
}

// 查找键对应的值
void *hashmap_get(HashMap *hashmap, const char *key) {
    unsigned int index = hash(key, hashmap->capacity);
    Node *current_node = hashmap->buckets[index];

    while (current_node != NULL) {
        if (strcmp(current_node->key, key) == 0) {
            return current_node->value;
        }
        current_node = current_node->next;
    }
    return NULL;
}

// 删除键值对
void hashmap_remove(HashMap *hashmap, const char *key) {
    unsigned int index = hash(key, hashmap->capacity);
    Node *current_node = hashmap->buckets[index];
    Node *prev_node = NULL;
    while (current_node != NULL) {
        if (strcmp(current_node->key, key) == 0) {
            if (prev_node == NULL) {
                // 删除链表头部
                hashmap->buckets[index] = current_node->next;
            } else {
                prev_node->next = current_node->next;
            }
            free(current_node->key);
            free(current_node);
            hashmap->size--;
            return;
        }
        prev_node = current_node;
        current_node = current_node->next;
    }
}

// 释放哈希表
void hashmap_free(HashMap *hashmap) {
    for (int i = 0; i < hashmap->capacity; i++) {
        Node *current_node = hashmap->buckets[i];
        while (current_node != NULL) {
            Node *temp_ndoe = current_node;
            current_node = current_node->next;
            free(temp_ndoe->key);
            free(temp_ndoe);
        }
    }
    free(hashmap->buckets);
    free(hashmap);
}